#
# peerscape.core.item
#
# Copyright 2007-2008 Helsinki Institute for Information Technology
# and the authors.
#
# Authors: Ken Rimey <rimey@hiit.fi>
#

# Permission is hereby granted, free of charge, to any person
# obtaining a copy of this software and associated documentation files
# (the "Software"), to deal in the Software without restriction,
# including without limitation the rights to use, copy, modify, merge,
# publish, distribute, sublicense, and/or sell copies of the Software,
# and to permit persons to whom the Software is furnished to do so,
# subject to the following conditions:
#
# The above copyright notice and this permission notice shall be
# included in all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
# IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
# CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
# TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
# SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

"""
Encoding for Tamper-Resistant Sharing

ETRS data comprises signed items, organized into datasets.  (These
correspond to messages and publications in information networking
terminology.)

Each dataset defines a key-value dictionary.  (This is our current
focus, but additional kinds of datasets are conceivable.)

There are currently two kinds of items: root items and key-value
items.  Key-value items represent updates to dictionary entries.

Each dataset has exactly one root item.  Items have IDs, and the ID
of a dataset's root item is the ID of the dataset.  We call it an
information ID.

An item is a list, whose first element defines the item type.  This is
currently either "root" or "kv".  Items are serialized as canonical
s-expressions (see peerscape.lib.sexp).

For a root item, the second element is a digest of the public key of
the creator.  For other items, the second element is the information
ID of the dataset.

The remaining elements of an item are lists called fields.  Each
specifies a unique field name and one or more field values.

Every item has a signature field ("sig").  A non-root item can also
have a secondary signature ("sig2").  Each signature is over the
serialized item with the signature fields removed.  Moreover, the ID
of an item is the SHA-1 hash of the same serialization (also excluding
the signatures).

The fields of an item appear in alphabetical order by field name, but
the signature fields always come last.

A root item looks like this, where the salt field is optional:

["root" fingerprint ["salt" salt] ["type" type] ["sig" signature public_key]]

The fingerprint, salt, and type are strings, while the signature and
the public key are list structures.

    fingerprint - SHA-1 hash of the serialization of the public key.

    salt - a string of random bytes.  This must be omitted if the
    dataset type is "principal".

    type - the dataset type encoded using UTF-8.

    signature - signature by the creator of the dataset.

    public_key - public key of the creator of the dataset.

The information ID of a dataset of type "principal" is solely a
function of the public key (via its fingerprint).  We use this
information ID as standard name for the principal represented by the
public key, and we use the dataset as a place to store information
about the principal.

A key-value item defines (an update to) a key-value pair:

["kv" iid ["key" key] ["seq" seq] ["value" value] ["sig" ...] ["sig2" ...]]

The value and sig2 fields are optional.

    iid - the information ID of the dataset to which the item belongs,
    represented as a 20-byte binary string.

    key - a list of one or more non-empty byte strings.

    seq - a sequence number, expressed in decimal.  This is a positive
    integer greater than the sequence numbers of any other items with
    the same key present in the local copy of the dataset when this
    item was originally created.

    value - a byte string of arbitrary length.  If the value field is
    omitted, the item is a tombstone representing a deleted key.

The signature field can take the same form as in a root item:

    ["sig" signature public_key]

However, if the signing principal is the creator of the dataset, the
signature field should omit the public key:

    ["sig" signature]

The optional secondary signature field is similar, except that the
field name is "sig2".

A dataset can define a group of principals.  This is done using auth
items, which are simply key-value items with a key whose first element
is "auth" and whose second element is a principal's information ID
expressed in hexadecimal.  (Although the canonical s-expression
encoding accommodates binary data, we prefer to avoid binary in keys,
which are exposed to applications.)  The value is a JSON object
specifying information about the principal, optionally including a
list of named roles assigned to the principal.

The creator of a dataset is always authorized to sign items belonging
to that dataset.  Policy items can be added to the dataset to
authorize other principals to sign particular kinds of items.  A
policy item is simply a key-value item with a key that starts with
"policy".  The value is a JSON object.  An important type of policy
item grants specified rights to all principals assigned a particular
role in some specified dataset.  See policy.py for the details.

The value of an auth or policy item is required to be a JSON object (a
map).  If the object includes a value for "roles", the value must be a
list of strings.

Normally each new key-value item supersedes all previous items with
the same key in that dataset.  An exception is made for auth and
policy items, however, so that history can be replayed correctly when
forwarding items from one node to another.  In general, superseded
versions are retained when a key is deleted or the value is updated if
and only if the first element of the key is "auth" or "policy".
"""

from os import urandom
from hashlib import sha1
from types import NoneType

from peerscape.lib import json
from peerscape.lib.sexp import encode, decode
from peerscape.core.identity import decode_identity
from peerscape.core.signature import decode_signature
from peerscape.core.iid import hex, hex_to_buffer

def init_doctest():
    """Initialize variables referred to in the doctests."""
    global root1, root2, root3, iid1, iid2, iid3, roots
    global kv1, kv2, kv3, kv4, auth, policy
    global items, root_items, kv_items

    from peerscape.core.identity import generate

    identity1 = generate(size=512)
    identity2 = generate(size=512)

    root1 = create_root_item(identity1)
    root2 = create_root_item(identity2)
    root3 = create_root_item(identity2, type='content')

    iid1 = root1.iid
    iid2 = root2.iid
    iid3 = root3.iid

    roots = {iid1: root1, iid2: root2, iid3: root3}

    kv1 = create_kv_item(iid1, ['favorite', 'color'], 'blue', 1, identity1)
    kv2 = create_kv_item(iid1, ['favorite', 'color'], 'violet', 2, identity1)
    kv3 = create_kv_item(iid1, ['favorite', 'color'], None, 3, identity1)

    auth = create_kv_item(iid2, ['auth', hex(iid1)], '{}', 1, identity2)
    auth.countersign(identity1)

    policy_key = ['policy', 'details not important here...']
    policy = create_kv_item(iid3, policy_key, '{}', 1, identity2)

    kv4 = create_kv_item(iid3, ['answer'], '42', 1, identity1)

    root_items = [root1, root2, root3]
    kv_items = [kv1, kv2, kv3, kv4, auth, policy]
    items = root_items + kv_items

    for item in kv_items:
        item.normalize(roots[item.iid])

class Item(object):
    """
    Abstract base class for root and kv items

    The following attributes are always defined: hash, iid, key, seq,
    sig, pk, sig2, pk2.

    The hash and iid are 20-byte binary buffers.
    """
    key = []                    # list
    seq = 1                     # positive integer
    sig = pk = None             # list
    sig2 = pk2 = None           # list

    def __cmp__(self, other):
        """
        Standard total order

        >>> kv1 < kv2 < kv3
        True
        >>> cmp(root1, root1)
        0
        """
        return cmp(self.seq, other.seq) or cmp(self.hash, other.hash)

    @property
    def hash(self):
        """
        >>> len(root1.hash)
        20
        """
        string = self.encode(omit_sigs=True)
        return buffer(sha1(string).digest())

    def sign(self, identity):
        """Add a primary signature to the item."""
        self.sig, self.pk = self.create_signature(identity)

    def countersign(self, identity):
        """Add a secondary signature to the item."""
        self.sig2, self.pk2 = self.create_signature(identity)

    def create_signature(self, identity):
        return (identity.sign(self.encode(omit_sigs=True)).export(),
                identity.export_public())

    def normalize(self, root):
        """Remove superfluous public keys from a signed item."""
        assert root.is_root() and self.iid == root.iid
        if not self.is_root():
            if self.pk == root.pk:
                self.pk = None
            if self.pk2 == root.pk:
                self.pk2 = None

    def get_signing_principal(self, root=None):
        """
        Return the information ID of the signing principal.

        >>> principals = {iid1: 1, iid2: 2}
        >>> [principals[item.get_signing_principal()]
        ...  for item in root_items]
        [1, 2, 2]
        >>> [principals[item.get_signing_principal(roots[item.iid])]
        ...  for item in kv_items]
        [1, 1, 1, 1, 2, 2]
        """
        if self.pk is None:
            assert root and root.is_root() and self.iid == root.iid
            return root.get_signing_principal()
        else:
            fingerprint = sha1(encode(self.pk)).digest()
            return RootItem(fingerprint, type='principal').hash

    def get_countersigning_principal(self, root=None):
        """
        Return the information ID of the countersigning principal.

        If there is no secondary signature, None is returned.

        >>> principals = {None: 0, iid1: 1, iid2: 2}
        >>> [principals[item.get_countersigning_principal()]
        ...  for item in root_items]
        [0, 0, 0]
        >>> [principals[item.get_countersigning_principal(roots[item.iid])]
        ...  for item in kv_items]
        [0, 0, 0, 0, 1, 0]
        """
        if self.sig2 is None:
            return None
        elif self.pk2 is None:
            assert root and root.is_root() and self.iid == root.iid
            return root.get_signing_principal()
        else:
            fingerprint = sha1(encode(self.pk2)).digest()
            return RootItem(fingerprint, type='principal').hash

    def is_root(self):
        """
        Return True if this is a root item.

        >>> [item.is_root() for item in items]
        [True, True, True, False, False, False, False, False, False]
        """
        return isinstance(self, RootItem)

    def is_kv(self):
        """
        Return True if this is a key-value item.

        >>> [item.is_kv() for item in items]
        [False, False, False, True, True, True, True, True, True]
        """
        return isinstance(self, KVItem)

    def is_auth(self):
        """
        Return True if this is an auth key-value item.

        >>> [item.is_auth() for item in items]
        [False, False, False, False, False, False, False, True, False]
        """
        return self.is_kv() and self.key[0] == 'auth'

    def is_policy(self):
        """
        Return True if this is an policy key-value item.

        >>> [item.is_policy() for item in items]
        [False, False, False, False, False, False, False, False, True]
        """
        return self.is_kv() and self.key[0] == 'policy'

    def validate(self):
        """
        Check the validity of the item, but not the signature or authorization.

        Raises ValueError if there is a problem.

        >>> all(item.validate() is None for item in items)
        True
        """
        for field, what in ((self.hash, buffer),
                            (self.iid, buffer),
                            (self.key, list),
                            (self.seq, int),
                            (self.sig, list),
                            (self.pk, (NoneType, list)),
                            (self.sig2, (NoneType, list)),
                            (self.pk2, (NoneType, list))):
            if not isinstance(field, what):
                raise ValueError

        for part in self.key:
            if not isinstance(part, str) or not part:
                raise ValueError

        if self.seq < 1:
            raise ValueError

        for sig, pk in [(self.sig, self.pk), (self.sig2, self.pk2)]:
            if sig is None and pk is not None:
                raise ValueError

            if sig is not None:
                decode_signature(sig)

            if pk is not None:
                decode_identity(pk)

    def verify_signatures(self, root=None):
        """
        Return True if the signatures are valid.

        The public key is retrieved from the specified root item if necessary.

        >>> all(item.verify_signatures() for item in root_items)
        True
        >>> all(item.verify_signatures(roots[item.iid]) for item in kv_items)
        True
        """
        for sig, pk in [(self.sig, self.pk), (self.sig2, self.pk2)]:
            if sig is not None:
                if pk is None:
                    assert root and root.is_root() and self.iid == root.iid
                    pk = root.pk

                try:
                    sig = decode_signature(sig)
                    identity = decode_identity(pk)
                    if not identity.verify(self.encode(omit_sigs=True), sig):
                        return False
                except ValueError:
                    return False
        else:
            return self.sig is not None

    def encode(self, omit_sigs=False):
        """Return a string encoding the item as a canonical s-expression."""
        data = self.export()
        if not omit_sigs:
            for name, sig, pk in [('sig', self.sig, self.pk),
                                  ('sig2', self.sig2, self.pk2)]:
                if sig is not None:
                    field = [name, sig]
                    if pk is not None:
                        field.append(pk)
                    data.append(field)

        return encode(data)

class RootItem(Item):
    def __init__(self, fingerprint, type, salt=None):
        self.fingerprint = fingerprint
        self.type = type if isinstance(type, unicode) else type.decode('utf-8')
        self.salt = salt

    @property
    def iid(self):
        return buffer(self.hash)

    def validate(self):
        Item.validate(self)
        if not isinstance(self.type, unicode):
            raise ValueError
        if self.salt is not None:
            if not isinstance(self.salt, str):
                raise ValueError
            if self.type == 'principal':
                raise ValueError
        if self.pk is None:
            raise ValueError
        if self.fingerprint != sha1(encode(self.pk)).digest():
            raise ValueError

    def export(self):
        data = ['root', self.fingerprint]
        if self.salt is not None:
            data.append(('salt', self.salt))
        data.append(('type', self.type))
        return data

    def to_sqlite(self):
        return dict(iid=self.iid,
                    type=self.type,
                    salt=bytes_to_sqlite(self.salt),
                    sig=list_to_sqlite(self.sig),
                    pk=list_to_sqlite(self.pk))

class KVItem(Item):
    def __init__(self, iid, key, seq, value=None):
        self.iid = buffer(iid)
        self.key = key
        self.seq = stdint(seq)
        self.value = value

    def validate(self):
        Item.validate(self)
        if not self.key:
            raise ValueError

        if not isinstance(self.value, (NoneType, str)):
            raise ValueError

        if self.key[0] in ('auth', 'policy') and self.value is not None:
            v = json.loads(self.value) # Can raise ValueError.
            if not isinstance(v, dict):
                raise ValueError
            if 'roles' in v:
                roles = v['roles']
                if not isinstance(roles, list):
                    raise ValueError
                if not all(isinstance(x, (str, unicode)) for x in roles):
                    raise ValueError

    def export(self):
        data = ['kv', str(self.iid)]
        data.append(('key', self.key))
        data.append(('seq', str(self.seq)))
        if self.value is not None:
            data.append(('value', self.value))
        return data

    def to_sqlite(self):
        return dict(hash=self.hash,
                    iid=self.iid,
                    key=list_to_sqlite(self.key),
                    seq=self.seq,
                    value=bytes_to_sqlite(self.value),
                    sig=list_to_sqlite(self.sig),
                    pk=list_to_sqlite(self.pk),
                    sig2=list_to_sqlite(self.sig2),
                    pk2=list_to_sqlite(self.pk2),
                    size=None if self.value is None else len(self.value))

def create_root_item(identity, type='principal'):
    """
    Construct a root item.

    identity -- Identity instance.
    type -- unicode string.
    """
    salt = None if type == 'principal' else urandom(20)
    item = RootItem(identity.digest(), type, salt)
    item.sign(identity)
    item.validate()
    return item

def create_kv_item(iid, key, value, seq, identity):
    """
    Construct a key-value item.

    iid -- information ID as a binary buffer or hexadecimal string.
    key -- list of strings.
    value -- string or None.
    seq -- positive integer.
    identity -- signing Identity instance.
    """
    iid = hex_to_buffer(iid)
    item = KVItem(iid, key, seq, value)
    item.sign(identity)
    item.validate()
    return item

def decode_item(sexp):
    """
    Construct an Item from an s-expression.

    The argument can be either a string or a list.

    >>> all(decode_item(item.encode()) == item for item in items)
    True
    """
    data = sexp if isinstance(sexp, list) else decode(sexp)

    name, sig, pk = pop_signature(data, ['sig', 'sig2'])
    if name != 'sig2':
        sig2, pk2 = None, None
    else:
        sig2, pk2 = sig, pk
        name, sig, pk = pop_signature(data, ['sig'])

    if len(data) < 2:
        raise ValueError

    item_type = data.pop(0)
    if item_type not in ('root', 'kv'):
        raise ValueError

    x = data.pop(0)
    if not isinstance(x, str):
        raise ValueError

    if not all(isinstance(field, list) for field in data):
        raise ValueError

    previous = ''
    for name, value in data:
        if not isinstance(name, str) or not previous < name:
            raise ValueError
        previous = name

    fields = dict(data)
    try:
        if item_type == 'root':
            item = RootItem(x, **fields) # Can raise TypeError.
        elif item_type == 'kv':
            item = KVItem(x, **fields)   # Can raise TypeError.
        else:
            raise ValueError
    except TypeError:
        raise ValueError

    item.sig, item.pk = sig, pk
    item.sig2, item.pk2 = sig2, pk2

    item.validate()
    return item

def pop_signature(data, labels):
    if data:
        field = data[-1]
        if isinstance(field, list) and field and field[0] in labels:
            if len(field) == 2:
                name, sig = field
                pk = None
            elif len(field) == 3:
                name, sig, pk = field
            else:
                raise ValueError

            del data[-1]
            return name, sig, pk

    return None, None, None

def root_item_from_sqlite(data):
    """
    Construct a root item from database columns.

    >>> all(root_item_from_sqlite(x.to_sqlite()) == x for x in root_items)
    True
    """
    type = data['type']
    salt = bytes_from_sqlite(data['salt'])
    sig = list_from_sqlite(data['sig'])
    pk = list_from_sqlite(data['pk'])

    fingerprint = sha1(encode(pk)).digest()
    item = RootItem(fingerprint, type, salt)
    item.sig, item.pk = sig, pk

    for k, v in item.to_sqlite().iteritems():
        assert data[k] == v

    item.num = data.get('num')
    item.validate()
    return item

def kv_item_from_sqlite(data):
    """
    Construct a key-value item from database columns.

    >>> all(kv_item_from_sqlite(x.to_sqlite()) == x for x in kv_items)
    True
    """
    iid = data['iid']
    key = list_from_sqlite(data['key'])
    seq = data['seq']
    value = bytes_from_sqlite(data['value'])
    sig = list_from_sqlite(data['sig'])
    pk = list_from_sqlite(data['pk'])
    sig2 = list_from_sqlite(data['sig2'])
    pk2 = list_from_sqlite(data['pk2'])

    item = KVItem(iid, key, seq, value)
    item.sig, item.pk = sig, pk
    item.sig2, item.pk2 = sig2, pk2

    for k, v in item.to_sqlite().iteritems():
        assert data[k] == v

    item.num = data.get('num')
    item.validate()
    return item

def bytes_to_sqlite(x): return buffer(x) if isinstance(x, str) else x
def list_to_sqlite(x): return buffer(encode(x)) if isinstance(x, list) else x

def bytes_from_sqlite(x): return str(x) if isinstance(x, buffer) else x
def list_from_sqlite(x): return decode(str(x)) if isinstance(x, buffer) else x

def stdint(x):
    """
    Parse a decimal number and check that it is in canonical form.

    The argument can be either a string or an integer.  If it is a
    non-canonical decimal (e.g., if it has leading or trailing
    whitespace or leading zeros), raise ValueError.

    >>> stdint(42)
    42
    >>> stdint("42")
    42
    >>> stdint(" 42")
    Traceback (most recent call last):
        ...
    ValueError
    >>> int(" 42")
    42
    """
    i = int(x)
    if i == x or str(i) == x:
        return i
    else:
        raise ValueError

if __name__ == '__main__':
    import doctest
    init_doctest()
    doctest.testmod()
